The present invention relates to a device and a method for retrieval, a recording medium, and a program that enable a plurality of associative memories to be used suitably.
FIG. 1 shows an example of configuration of an associative memory (content addressable memory (CAM)) 1.
An input control unit 11 latches externally inputted data for retrieval (retrieval data), for example, and then supplies the data to a mask register 12.
On the basis of a mask data selection signal inputted from the input control unit 11, the mask register 12 supplies a CAM block 13 with mask data stored in the mask register 12 to mask a data portion not associated with retrieval.
The CAM block 13 has a plurality of m-bit word memories 21-1, 21-2, . . . , as shown in FIG. 2. (The word memories will be referred to as word memories 21 where they do not need to be individually distinguished from each other. The same is true for other cases.) The word memories 21 can store (enter) therein data to be retrieved (stored data) and a logical value (hereinafter referred to as an empty bit) indicating that the stored data is set as data to be retrieved or not set as data to be retrieved, for example.
Incidentally, when an empty bit indicating that the stored data is not set as data to be retrieved is set, the word memory 21 is treated as a word memory 21 that can store new data when the new data is stored in the CAM 1. Therefore the setting of the empty bit means deletion of the stored data (setting the word memory 21 in an empty state).
In this example, the empty bit indicating that the stored data is set as data to be retrieved (the word memory 21 is not in the empty state) is a logical value 0, while the empty bit indicating that the stored data is not set as data to be retrieved (the word memory 21 is in the empty state) is a logical value 1.
Returning to FIG. 1, a plurality of signal lines 14 (represented by a single line for simplicity in the figure) corresponding to the respective word memories 21 of the CAM block 13 are provided between the CAM block 13 and an output control unit 16. Receiving an instruction to retrieve word memories 21 in the empty state (hereinafter referred to as empty address retrieval) from a control unit 17, the CAM block 13 outputs a logical value (logical value 1) indicating that a word memory 21 is not in the empty state from the signal line 14 of the word memory 21 having an empty bit of the logical value 0 indicating that the word memory 21 is not in the empty state to the output control unit 16. Also, the CAM block 13 outputs a logical value (logical value 0) indicating that a word memory 21 is in the empty state from the signal line 14 of the word memory 21 having an empty bit of the logical value 1 indicating that the word memory 21 is in the empty state to the output control unit 16.
A plurality of signal lines 15 (represented by a single line for simplicity in the figure) corresponding to the respective word memories 21 are further provided between the CAM block 13 and the output control unit 16.
Receiving an instruction to retrieve word memories 21 on the basis of retrieval data (hereinafter referred to as hit address retrieval) from the control unit 17, the CAM block 13 outputs a logical value (logical value 0, for example) indicating a hit to the output control unit 16 from the signal line 15 of the word memory 21 that has an empty bit of the logical value 0 indicating that the word memory 21 is not in the empty state and which stores stored data having a bit pattern matching a portion of the retrieval data that is not masked by the mask register 12. Also, the CAM block 13 outputs a logical value (logical value 1, for example) indicating no hit (a miss) to the output control unit 16 from the signal line 15 of the word memory 21 that has an empty bit of the logical value 0 indicating that the word memory 21 is not in the empty state but which does not store stored data having a bit pattern matching a portion of the retrieval data that is not masked by the mask register 12, or the word memory 21 having an empty bit of the logical value 1 indicating that the word memory 21 is in the empty state.
In the hit address retrieval, the CAM block 13 notifies a result of the retrieval (indicating a hit or a miss) to the control unit 17 as required.
When receiving an instruction for empty address retrieval from the control unit 17, the output control unit 16 detects an address of highest priority (lowest number, for example) from among addresses of word memories 21 corresponding to signal lines 14 that have outputted the logical value indicating that the word memories 21 are in the empty state. The output control unit 16 outputs the address as an address HEA (Highest Empty Address).
Also, when receiving an instruction for hit address retrieval from the control unit 17, the output control unit 16 detects an address of highest priority (lowest number in this example) from among addresses of word memories 21 corresponding to signal lines 15 that have outputted the logical value indicating a hit. The output control unit 16 outputs the address as an address HHA (Highest Hit Address).
The control unit 17 controls each part according to an external control signal. For example, the control unit 17 controls the CAM block 13 and the output control unit 16 to perform empty address retrieval or hit address retrieval based on retrieval data inputted by the input control unit 11. The control unit 17 outputs a result of the hit address retrieval inputted from the CAM block 13 to the outside as required.
The control unit 17 can control the CAM block 13 to store data inputted by the input control unit 11 in the word memory 21 of the address HEA or the address HHA obtained by the empty address retrieval or the hit address retrieval. At this time, the control unit 17 can store the input data in a predetermined part of the word memory 21 using mask data of the mask register 12 (that is, the control unit 17 can change the predetermined part of the word memory 21).
Incidentally, the control unit 17 can control the CAM block 13 and the output control unit 16 to read stored data from the word memory 21 corresponding to an address inputted by the input control unit 11 or write data further inputted by the input control unit 11 to the word memory 21 at the address, as in a normal RAM.
FIG. 3 shows an example of configuration of a network frame repeater 31 using the CAM 1 described above (see Japanese Patent Laid-Open No. Hei 10-255485). The repeater 31 is connected with two networks 32-1 and 32-2. The network 32-1 is connected with three terminals 33-11 to 33-13. The network 32-2 is connected with three terminals 33-21 to 33-23. The repeater 31 is a so-called hub for relaying network frames transmitted and received between terminals 33.
A CPU 41 of the repeater 31 is connected with a packet memory 42, a CAM 1, a RAM 43, and port controllers 45-1 and 45-2 via a bus 46, and controls each of the parts.
The packet memory 42 temporarily stores packets of network frames transmitted to the repeater 31.
Word memories 21 of the CAM 1 (CAM block 13) in this case store addresses on the networks of the terminals 33-11 to 33-13 and the terminals 33-21 to 33-23 and time stamps, as shown in FIG. 4.
The repeater 31 manages time by changing numbers of p time slots in order at predetermined time intervals, as shown in FIG. 5. The time stamps represent the numbers 1, 2, . . . , p of the time slots. Incidentally, a method of using the time stamp will be described later.
Returning to FIG. 3, the RAM 43 stores a port number indicating a port 47 via which each terminal 33 is connected. Incidentally, though not described in detail, the RAM 43 stores data of a VLAN (Virtual LAN), data referred to by hardware of the repeater 31, and the like.
An address of each word memory 21 of the CAM 1 and an address of each memory area of the RAM 43 are associated with each other by a signal line 44.
The CAM 1, having a retrieval function added thereto, requires a high cost per bit and has a relatively low memory capacity as compared with ordinary RAMs. Therefore, the CAM 1 and the RAM 43 can be used concurrently as in this example.
The two port controllers 45-1 and 45-2 are connected to the networks 32-1 and 32-2 via ports 47-1 and 47-2. The port controllers 45-1 and 45-2 transmit data supplied from the CPU 41 to a predetermined terminal 33 via the network 32. The port controllers 45-1 and 45-2 also receive data transmitted from a terminal 33, and then supply the data to the CPU 41.
Operation of the repeater 31 will next be described with reference to a flowchart of FIG. 6.
At a step S1, the CPU 41 controls the CAM 1 to start empty address retrieval and processing for securing word memories 21 in an empty state.
Thereby the CAM 1 starts processing (empty address retrieval) for retrieving word memories 21 in the empty state (word memories 21 having an empty bit indicating that the word memory 21 is in the empty state), detecting a highest-priority address (lowest-number address) among addresses of the retrieved word memories 21, and outputting the address as an address HEA. The CAM 1 also starts processing for retrieving word memories 21 storing a number of a time slot (time stamp) preceding a time slot at a present time supplied from the CPU 41 as required, and changing empty bits of the retrieved word memories 21 to a logical value indicating that the word memories 21 are in the empty state (processing for deleting stored data of the predetermined word memories 21 and securing the word memories 21 in the empty state).
At a next step S2, the CPU 41 stands by until a network frame is inputted from the port controller 45 via the bus 46. When a network frame is inputted, the CPU 41 proceeds to a step S3.
At the step S3, the CPU 41 temporarily stores the inputted network frame in the packet memory 42, and extracts a destination address DA indicating a destination of data transfer (transmission) from a header portion of the stored network frame. Then, the CPU 41 controls the CAM 1 to perform hit address retrieval using the destination address DA as retrieval data.
Incidentally, the header portion of the network frame stores the destination address DA, a source address SA indicating a transmission source, and the like.
The CAM 1 performs hit address retrieval on the basis of the retrieval data (the address DA in this case) supplied from the CPU 41. When the CAM 1 can detect an address HHA in the hit address retrieval, the CAM 1 notifies the hit to the CPU 41, and outputs the address HHA to the RAM 43 via the signal line 44. Incidentally, the address of a terminal 33 as the transmission destination is stored in a word memory 21 of the CAM 1 (CAM block 13).
The CPU 41 reads, from the RAM 43, a port number stored in a memory area corresponding to the address HHA detected by the CAM 1.
At a next step S4, the CPU 41 transmits the network frame inputted at the step S2 to the destination terminal 33 via the port 47 corresponding to the port number read at the step S3 and the network 32.
At a step S5, the CPU 41 extracts the source address SA indicating the transmission source from the network frame stored in the packet memory 42, and controls the CAM 1 to perform hit address retrieval using the source address SA as retrieval data.
Thereby the CAM 1 performs hit address retrieval based on the retrieval data (the address SA in this case) from the CPU 41, and then notifies a result of the hit address retrieval to the CPU 41.
At a step S6, the CPU 41 determines whether or not an address HHA is detected on the basis of the notification from the CAM 1. When the CPU 41 determines that an address HHA is detected (when the address SA of the transmission source is stored in a word memory 21), the CPU 41 proceeds to a step S7.
At the step S7, the CPU 41 controls the CAM 1 to update the time stamp. Thereby the CAM 1 replaces the time stamp in the word memory 21 corresponding to the address HHA with the time stamp at the present time supplied from the CPU 41. When the time stamp of a terminal 33 as the transmission source (a terminal 33 using the repeater 31) is thus updated, the address of the terminal 33 on the network is not deleted in the processing of the step S1. Hence, in the processing of the step S1, addresses of terminals 33 that have not used the repeater 31 recently are deleted to secure word memories 21 in the empty state.
When the CPU 41 determines at the step S6 that no address HHA is detected, the CPU 41 proceeds to a step S8, where the CPU 41 controls the CAM 1 to store the source address SA of the transmission source and the time stamp at the present time.
Thereby the CAM 1 stores the source address SA and the time stamp at the present time supplied from the CPU 41 in the word memory 21 of the address HEA (the word memory 21 in the empty state) detected in the processing of the step S1. At this time, the CPU 41 stores a port number of the inputted network frame in a memory area of the RAM 43 which area corresponds to the address HEA.
After the processing of the step S7 or the step S8 is performed, the CPU 41 returns to the step S2 to repeat the processing from the step S2 on down.
In the example of FIG. 3, the stored data is relatively small in amount, representing the network addresses of the six terminals 33 and time stamps. However, when a number of terminals 33 for relay is increased and the stored data becomes larger in data amount (when a number of entries is increased), one CAM 1 cannot manage the data. In this case, as shown in FIG. 7, for example, a plurality of CAMs 1 (four CAMs 1-1 to 1-4 in the example of FIG. 7) are used in cascade connection (to be described later in detail). Incidentally, the CAMs 1-1 to 1-4 as a whole will be referred to as a connected CAM 2 as appropriate.
Addresses of word memories 21 of the CAMs 1-1 to 1-4 including the connected CAM 2 are set in order from the CAM 1-1 to the CAM 1-4, as shown in FIG. 8. Specifically, in terms of the CAM 1 units, the CAM 1-1 has addresses of highest priority; the CAM 1-2 has addresses of priority next to that of the CAM 1-1; the CAM 1-3 has addresses of priority next to that of the CAM 1-2; and the CAM 1-4 has addresses of lowest priority.
Also in this case, the connected CAM 2 as a whole outputs one address HHA or address HEA as a result of empty address retrieval or hit address retrieval. In detection of the address HHA or address HEA, the CAMs 1 ultimately have priority (precedence) in order of the CAM 1-1, the CAM 1-2, the CAM 1-3, and the CAM 1-4.
Main operation of the connected CAM 2 will be described in the following. When the connected CAM 2 performs empty address retrieval (step S1 in FIG. 6), each CAM 1 performs empty address retrieval, and transmits a result of the empty address retrieval to CAMs 1 of lower priority than the CAM 1 itself, as shown by signal lines 61 in FIG. 7. Specifically, a result of the retrieval of the CAM 1-1 is transmitted to the CAM 1-2 (signal line 61-3), the CAM 1-3 (signal line 61-2), and the CAM 1-4 (signal line 61-1). A result of the retrieval of the CAM 1-2 is transmitted to the CAM 1-3 (signal line 61-5) and the CAM 1-4 (signal line 61-4). A result of the retrieval of the CAM 1-3 is transmitted to the CAM 1-4 (signal line 61-6).
Each CAM 1 detects and outputs an address HEA according to a result of the retrieval of the CAMs 1 of higher priority than the CAM 1 itself.
Specifically, since the CAM 1-1 has the highest priority, when the CAM 1-1 can retrieve a word memory 21 in an empty state from a CAM block 13 of the CAM 1-1 itself, the CAM 1-1 detects an address HEA from an address of the retrieved word memory 21, and then outputs the address HEA. That is, in this case, the address HEA of the CAM 1-1 is outputted as the address HEA of the connected CAM 2.
In the case where the CAM 1-1 retrieves the word memory 21 in the empty state, the CAM 1-2 does not output an address HEA even when a word memory 21 in the empty state is retrieved from a CAM block 13 of the CAM 1-2 itself. When the CAM 1-1 does not retrieve a word memory 21 in the empty state, on the other hand, the CAM 1-2 detects the address HEA from an address of the word memory 21 in the empty state retrieved by the CAM 1-2 itself, and then outputs the address HEA. That is, in this case, the address HEA of the CAM 1-2 is outputted as the address HEA of the connected CAM 2.
In the case where one of the CAMs 1-1 and 1-2 retrieves the word memory 21 in the empty state, the CAM 1-3 does not output an address HEA even when a word memory 21 in the empty state is retrieved from a CAM block 13 of the CAM 1-3 itself. When none of the CAMs 1-1 and 1-2 retrieve a word memory 21 in the empty state, on the other hand, the CAM 1-3 detects the address HEA from an address of the word memory 21 in the empty state retrieved by the CAM 1-3 itself, and then outputs the address HEA. That is, in this case, the address HEA of the CAM 1-3 is outputted as the address HEA of the connected CAM 2.
In the case where one of the CAMs 1-1, 1-2, and 1-3 retrieves the word memory 21 in the empty state, the CAM 1-4 does not output an address HEA even when a word memory 21 in the empty state is retrieved from a CAM block 13 of the CAM 1-4 itself. When none of the CAMs 1-1, 1-2, and 1-3 retrieve a word memory 21 in the empty state, on the other hand, the CAM 1-4 detects the address HEA from an address of the word memory 21 retrieved by the CAM 1-4 itself, and then outputs the address HEA. That is, in this case, the address HEA of the CAM 1-4 is outputted as the address HEA of the connected CAM 2.
Thus, the address HEA of the connected CAM 2 as a whole is detected. Incidentally, the address HEA thus detected is supplied to a RAM 43 via a signal line 44.
When the connected CAM 2 performs hit address retrieval (step S5 in FIG. 6), each CAM 1 performs hit address retrieval based on retrieval data (source address SA) from a CPU 41, and then transmits a result of the retrieval to both CAMs 1 of higher priority than the CAM 1 itself and CAMs 1 of lower priority than the CAM 1 itself (transmits the result to the other CAMs 1), as indicated by signal lines 71 in FIG. 7.
Specifically, a result of the retrieval of the CAM 1-1 is transmitted to the CAM 1-2 (signal line 71-3), the CAM 1-3 (signal line 71-2), and the CAM 1-4 (signal line 71-1). A result of the retrieval of the CAM 1-2 is transmitted to the CAM 1-1 (signal line 71-3), the CAM 1-3 (signal line 71-5), and the CAM 1-4 (signal line 71-4). A result of the retrieval of the CAM 1-3 is transmitted to the CAM 1-1 (signal line 71-2), the CAM 1-2 (signal line 71-5), and the CAM 1-4 (signal line 71-6). A result of the retrieval of the CAM 1-4 is transmitted to the CAM 1-1 (signal line 71-1), the CAM 1-2 (signal line 71-4), and the CAM -1-3 (signal line 71-6).
Each CAM 1 detects and outputs an address HHA according to a result of the retrieval of the CAMs 1 of higher priority than the CAM 1 itself.
Specifically, when the CAM 1-1 hits as a result of searching the CAM 1-1 itself, the CAM 1-1 detects an address HHA from an address of a retrieved word memory 21, and then outputs the address HHA regardless of results of the retrieval of the CAMs 1-2 to 1-4 (even when there is a hit in the CAMs 1-2 to 1-4).
In the case where the CAM 1-1 hits, the CAM 1-2 does not output an address HHA even when the CAM 1-2 itself hits. When the CAM 1-1 misses, on the other hand, the CAM 1-2 detects an address HHA from an address of a word memory 21 retrieved by the CAM 1-2 itself, and then outputs the address HHA.
In the case where one of the CAMs 1-1 and 1-2 hits, the CAM 1-3 does not output an address HHA even when the CAM 1-3 itself hits. When each of the CAMs 1-1 and 1-2 misses, on the other hand, the CAM 1-3 detects an address HHA from an address of a word memory 21 retrieved by the CAM 1-3 itself, and then outputs the address HHA.
In the case where one of the CAMs 1-1, 1-2, and 1-3 hits, the CAM 1-4 does not output an address HHA even when the CAM 1-4 itself hits. When each of the CAMs 1-1, 1-2, and 1-3 misses, on the other hand, the CAM 1-4 detects an address HHA from an address of a word memory 21 retrieved by the CAM 1-4 itself, and then outputs the address HHA.
Thus, the address HHA of the connected CAM 2 as a whole is detected. Incidentally, the address HHA thus detected is supplied to the RAM 43 via the signal line 44.
When the connected CAM 2 as a whole detects one address HHA and updates a time stamp in the word memory 21 corresponding to the address HHA (step S7 in FIG. 6), the CAM 1 that has detected the address HHA as described above updates the time stamp in the word memory 21 corresponding to the address HHA.
When the connected CAM 2 as a whole does not detect an address HHA and stores a source address SA and a time stamp at a present time at the address HEA (step S8), the CAM 1 that has detected the address HEA as described above stores the source address SA and the like in the word memory 21 of the address HEA.
Thus, the hit address retrieval (step S5) and the updating of the time stamp (step S7) or the storing of the source address SA and the like (step S8) on the basis of a result of the hit address retrieval are performed. These three steps will hereinafter be referred to collectively as auto-store processing as appropriate.
However, the CAMs 1 and the signal lines 71 shown in FIG. 7 are connected in a complex manner as shown in FIG. 9.
For this connection, each CAM 1 has one output terminal 81, three input terminals 82A to 82C, and three input terminals 83A to 83C. The output terminal 81 outputs a result of hit address retrieval. The input terminals 82 are supplied with results of hit address retrieval of the CAMs 1 of higher priority than the CAM 1 itself. The input terminals 83 are supplied with results of hit address retrieval of the CAMs 1 of lower priority than the CAM 1 itself.
Each CAM 1 will be described. The output terminal 81-1 of the CAM 1-1 is connected to the input terminals 82-2C, 82-3C, and 82-4C of their respective CAMs 1-2, 1-3, and 1-4, and outputs a result (logical value 1 or 0) of hit address retrieval of the CAM 1-1 to the input terminals 82-2C, 82-3C, and 82-4C. Since there are no CAMs 1 of higher priority than the CAM 1-1, the input terminals 82-1A to 82-1C of the CAM 1-1 are pulled up to ignore inputs to the input terminals 82-1A to 82-1C, The input terminals 83-1A, 83-1B, and 83-1C are connected to the output terminals 81-2, 81-3, and 81-4 of their respective CAMs 1-2, 1-3, and 1-4, and are supplied with retrieval results of the CAMs 1-2, 1-3, and 1-4.
The output terminal 81-2 of the CAM 1-2 is connected to the input terminals 83-1A, 82-3B, and 82-4B of their respective CAMs 1-1, 1-3, and 1-4, and outputs a result (logical value 1 or 0) of hit address retrieval of the CAM 1-2 to the input terminals 83-1A, 82-3B, and 82-4B. The input terminal 82-2C is connected to the output terminal 81-1 of the CAM 1-1, and is supplied with a retrieval result of the CAM 1-1. Since only the CAM 1-1 is of higher priority than the CAM 1-2, the remaining input terminals 82-2A and 82-2B of the CAM 1-2 are pulled up to ignore inputs to the input terminals 82-2A and 82-2B. The input terminals 83-2B and 83-2C are connected to the output terminals 81-3 and 81-4 of their respcetive CAMs 1-3 and 1-4, and are supplied with retrieval results of the CAMs 1-3 and 1-4. Since only the CAMs 1-3 and 1-4 are of lower priority than the CAM 1-2, the remaining input terminal 83-2A is pulled up to ignore inputs to the input terminal 83-2A.
The output terminal 81-3 of the CAM 1-3 is connected to the input terminals 83-1B, 83-2B, and 82-4A of their respective CAMs 1-1, 1-2, and 1-4, and outputs a retrieval result of the CAM 1-3 to the input terminals 83-1B, 83-2B, and 82-4A. The input terminals 82-3B and 82-3C are connected to the output terminals 81-2 and 81-1 of their respective CAMs 1-2 and 1-1, and are supplied with retrieval results of the CAMs 1-2 and 1-1. Since only the CAMs 1-1 and 1-2 are of higher priority than the CAM 1-3, the remaining input terminal 82-3A is pulled up to ignore inputs to the input terminal 82-3A. The input terminal 83-3C is connected to the output terminal 81-4 of the CAM 1-4, and is supplied with a retrieval result of the CAM 1-4. Since only the CAM 1-4 is of lower priority than the CAM 1-3, the remaining input terminals 83-3A and 83-3B are pulled up to ignore inputs to the input terminals 83-3A and 83-3B.
The output terminal 81-4 of the CAM 1-4 is connected to their respective input terminals 83-1C, 83-2C, and 83-3C of the CAMs 1-1, 1-2, and 1-3, and outputs a retrieval result of the CAM 1-4 to the input terminals 83-1C, 83-2C, and 83-3C. The input terminals 82-4A, 82-4B, and 82-4C are connected to the output terminals 81-3, 81-2, and 81-1 of their respective CAMs 1-3, 1-2, and 1-1, and are supplied with retrieval results of the CAMs 1-3, 1-2, and 1-1. Since there are no CAMs 1 of lower priority than the CAM 1-4, the input terminals 83-4A to 83-4C are pulled up to ignore inputs to the input terminals 83-4A to 83-4C.
When a signal of a logical value 1 is inputted to all the input terminals 82A, 82B, and 82C of the CAM 1 (when the CAMs 1 of higher priority than the CAM 1 miss), the CAM 1 detects an address HHA from an address of a word memory 21 retrieved by the CAM 1 itself, and updates a time stamp in the word memory 21 of the address HHA.
When the connected CAM 2 as a whole misses (when a signal of the logical value 1 is inputted to all the input terminals 82 and 83 of each CAM 1), the CAM 1 stores an address SA and the like in a word memory 21 of a detected address HEA.
Incidentally, the output of the output terminal 81 and the input of the input terminals 82 and 83 of each CAM 1 are controlled by a control unit 17 as shown in FIG. 10.
Thus, conventionally, each CAM 1 has the input terminals 82 and the input terminals 83 for inputting retrieval results from CAMs 1 of higher priority than the CAM 1 itself and from CAMs 1 of lower priority than the CAM 1 itself separately from each other (each CAM 1 has the input terminals 82 and the input terminals 83 that are each smaller in number by one than the number of CAMs 1 comprising the connected CAM 2 (3 (=4−1) in the example of FIG. 9)). Therefore the connection of the input terminals 82 and the input terminals 83 with the output terminals 81 of the CAMs 1 is complex, and thus the configuration of the connected CAM 2 is complex.
Incidentally, although it is possible to grasp a retrieval result of each CAM 1 by an open drain system, the processing cannot be performed rapidly.